The present invention relates to computer-aided design (CAD) tools for analyzing integrated circuits and, more particularly, to a transistor autosizer that minimizes delay and power consumption of a CMOS circuit.
In CMOS integrated circuit design, it is well known that the size of a transistor can affect its performance. Transistor sizing therefore has been an important design technique in tuning the performance of a circuit. The most popular design criteria considered in transistor sizing includes area, delay and power. To ensure that transistor sizing is proceeding toward an optimal result, the relationship between these design criteria and transistor size must be addressed.
In the popular Elmore delay model, the delay of a MOS circuit is computed by the RC time constant. The values of resistance R and capacitance C can be extracted from the elements in a circuit. A MOS transistor is modeled as a switch. This switch is controlled by the voltage at the gate. When the switch is on, there is a resistance R between source and drain. In addition, there are capacitances on three terminals: drain, source and gate. Both conducting resistance and capacitance can be controlled by changing the widths of the transistors.
In digital design, the delay of a MOS circuit is determined by the delay of the critical path, which can be computed from the summation of the delays of stages along this path (each stage is separated by the gate of a MOS transistor), as represented by Equation 1 (EQ 1): ##EQU1## R.sub.i is the conducting resistance of the transistor along the path that drives node i. C.sub.i is the node capacitance of node i. For a transistor, the conducting resistance is inversely proportional to the width of the transistor gate while the terminal capacitance is proportional to the width of the gate. Increasing the transistor width can reduce the resistance of this transistor, and thus reduce the delay of this stage. However, it also increases the loading capacitance of the previous stage, which increases the delay of the previous stage.
Regarding power, Equation 2 (EQ 2) is widely adopted in estimating the power consumption of a circuit: ##EQU2## Vdd is the power supply voltage, f is the clock frequency, and P.sub.i is the toggling probability of node i in a clock cycle (i.e., P.sub.i indicates probability of a delay in a particular gate toggling from one logic state to another due to the delay of an input). With respect to capacitance, it seems straightforward that reducing the transistor sizes can reduce the power. However, since toggling probability heavily depends on the transistor delays, reducing capacitance alone does not necessarily reduce the power. In addition, Equation 2 only considers the charging/discharging power consumed in the capacitors. It does not capture the DC leakage and short-circuit power, which is significant for some types of circuits.
Equations 1 and 2 represent simplified models of circuit delay and power consumption. Although simplified, these models illustrate the non-trivial nature of determining optimal sizes of transistors in order to minimize delay and power.
Most previous transistor autosizers focus on reducing transistor delay and area. (See, for example, J. Fishburn et al., "TILOS: A Posynomial Programming Approach to Transistor Sizing," Proceedings of the International Conference on Computer-Aided Design, pages 326-328 (1985) ("Fishburn"); K. Hedlund, "Electrical Optimization of PLAs," Proceedings of the Design Automation Conference, pages 681-687 (June 1985); A. E. Ruehli et al., "Analytical Power/Timing Optimization Technique for Digital System," Proceedings of the Design Automation Conference, pages 142-146 (June 1977); and U.S. Pat. No. 4,827,428 issued to Dunlop et al. Some approaches use area as a first-order estimation for power. Due to the correlation between delay and power, however, reducing area does not necessarily reduce the power.
Early transistor autosizers typically rely on heuristic approaches. However, due to poor efficiency, some of these approaches can only focus on the delay of a few critical paths rather than the whole circuit.
As an improvement to these early autosizers, the transistor sizing problem has been formulated as a posynomial programming problem based on a simplified delay model. Fishburn. Posynomial programming, a subfield of convex programming, includes the advantageous property of convexity, which guarantees that a local minimum is also a global minimum. However, due to the intractability of posynomial programming, a heuristic approximation has been proposed. Instead of determining the sizes of all the transistors simultaneously, this approximation only changes the size of one transistor each time. It first computes the delay sensitivity with respect to the transistor sizes, and then selects the most sensitive transistor to resize.
A problem with this approach is that resizing one transistor each time is very inefficient, especially when many transistors must be resized. Another problem is that posynomial programming always starts from the circuit having the smallest size. However, the smallest size circuit is not necessarily the best starting point. Moreover, the heuristic approximation will cause deviations from the optimal solution when the optimal solution is far from the starting point.
To guarantee an optimal solution, a true convex programming approach for transistor sizing is proposed. See, S. Sapatnekar et al., "An Exact Solution to the Transistor Sizing Problem for CMOS Circuits Using Convex Optimization," IEEE Transactions on Computer-Aided Design, pages 1621-1634, Vol. 12 (11) (November 1993). However, the intractability of convex programming makes it difficult to apply to large circuits and complex device models.
To overcome the efficiency and convergence problems of convex programming, a linear programming approach has been proposed. M. Berkelaar et al., "Computing the Entire Active Area/Power Consumption versus Delay Trade-Off Curve for Gate Sizing with a Piecewise Linear Simulator," Proceedings of the International Conference on Computer-Aided Design, pages 474-480 (November 1994). This approach represents design criteria in terms of linear equations and constraints as linear inequalities. A problem with this approach is that the delay and power of a transistor is not ideally a linear equation of its size. Modifications to this approach that ignore nonlinear effects and incorporate piece-wise linear approximation have been proposed. These modifications will decrease precision and increase the number of constraints.
Another problem with linear programming is numerical instability which typically appears when the problem size grows (in terms of the number of variables and constraints).
In summary, previous approaches for transistor autosizing suffer from a variety of drawbacks including the consideration of only a limited number of design criteria (i.e., delay and area); use of inefficient heuristic methodologies or approximations; intractability of certain types of programming; convergence problems of posynomial programming when used with approximations; inaccuracy of linear programming approximations; and the inherent instability of linear programming when applied to a large number of variables and constraints. The detrimental impact of these drawbacks is enhanced when autosizing is applied to deep sub-micron semiconductor technology.
Accordingly, a new method for transistor sizing is required that captures circuit effects ignored by previous approaches, efficiently and reliably calculates optimal transistor sizes and allows for easier control of the optimization process.